package cn.edu.njust.alg;


public class Pow2 {

	public static int powr(int n) {
		if (n == 0) {
			return 1;
		} else if ((n & 1) == 0) {
			return powr(n >> 1) * powr(n >> 1);
		} else {
			return 2 * powr(n >> 1) * powr(n >> 1);
		}
	}

	public static long quickpow(int n, int base) {

		long temp = base;
		long mulit = 1;
		while (n != 0) {
			if ((1 & n) == 1) {
				mulit *= temp;
			}
			temp = temp * temp;
			n = n >> 1;
		}

		return mulit;
	}

	public static void main(String[] args) {
		int n = 16;
		System.out.println(powr(n));
		System.out.println(quickpow(n, 2));
		System.out.println(Math.pow(2, n));
	}

}
